package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/all-oone-data-structure/">全 O(1) 的数据结构(All O`one Data Structure)</a>
 * <p>请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。</p>
 * <p>
 * 实现 AllOne 类：
 *     <ul>
 *         <li>AllOne() 初始化数据结构的对象。</li>
 *         <li>inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。</li>
 *         <li>dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。</li>
 *         <li>getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。</li>
 *         <li>getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。</li>
 *     </ul>
 * </p>
 * <p>注意：每个函数都应当满足 O(1) 平均时间复杂度。</p>
 *
 * <p>
 * <pre>
 * 示例 1：
 *      输入
 *          ["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", "getMinKey"]
 *          [[], ["hello"], ["hello"], [], [], ["leet"], [], []]
 *      输出
 *          [null, null, null, "hello", "hello", null, "hello", "leet"]
 *      解释
 *          AllOne allOne = new AllOne();
 *          allOne.inc("hello");
 *          allOne.inc("hello");
 *          allOne.getMaxKey(); // 返回 "hello"
 *          allOne.getMinKey(); // 返回 "hello"
 *          allOne.inc("leet");
 *          allOne.getMaxKey(); // 返回 "hello"
 *          allOne.getMinKey(); // 返回 "leet"
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= key.length <= 10</li>
 *     <li>key 由小写英文字母组成</li>
 *     <li>测试用例保证：在每次调用 dec 时，数据结构中总存在 key</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/15 9:30
 */
public class LC0432AllO1DataStructure_H {

    static class AllOne {

        private final Map<String, ListNode> map;
        private final ListNode head;
        private final ListNode tail;

        public AllOne() {
            map = new HashMap<>();
            head = new ListNode();
            tail = new ListNode();
            head.next = tail;
            tail.prev = head;
        }

        public void inc(String key) {
            // 如果当前key已存在，需要从count的listNode转移到count+1的listNode。如果不存在需要创建
            ListNode targetNode;
            if (map.containsKey(key)) {
                ListNode currNode = map.get(key);
                currNode.keys.remove(key);
                targetNode = currNode.next;
                if (targetNode != tail && currNode.count + 1 == targetNode.count) {
                    // 添加到next数组中即可
                    targetNode.keys.add(key);
                } else {
                    // 不存在合适的next节点：创建节点并修改指针
                    targetNode = new ListNode(currNode.count + 1, key, currNode, currNode.next);
                }
                // 移除当前节点
                if (currNode.keys.size() == 0) {
                    removeNode(currNode);
                }
            } else {
                // 如果当前key第一次出现。将当前key添加到count为1的listNode中。如果不存在需要创建
                targetNode = head.next;
                if (targetNode != tail && targetNode.count == 1) {
                    targetNode.keys.add(key);
                } else {
                    targetNode = new ListNode(1, key, head, head.next);
                }
            }
            map.put(key, targetNode);
        }

        public void dec(String key) {
            // 题目保证调用dec方法时key对应的count>=1
            // 一定存在
            ListNode currNode = map.get(key);
            currNode.keys.remove(key);
            // 1.转移当前key到count-1对应listNode中
            if (currNode.count == 1) {
                map.remove(key);
            } else {
                ListNode targetNode = currNode.prev;
                if (targetNode != head && targetNode.count + 1 == currNode.count) {
                    targetNode.keys.add(key);
                } else {
                    targetNode = new ListNode(currNode.count - 1, key, currNode.prev, currNode);
                }
                map.put(key, targetNode);
            }
            if (currNode.keys.size() == 0) {
                removeNode(currNode);
            }
        }

        public String getMaxKey() {
            if (tail.prev == head) {
                return "";
            }
            return tail.prev.keys.get(0);
        }

        public String getMinKey() {
            if (head.next == tail) {
                return "";
            }
            return head.next.keys.get(0);
        }

        private void removeNode(ListNode currNode) {
            currNode.prev.next = currNode.next;
            currNode.next.prev = currNode.prev;
        }

        static class ListNode {
            private final List<String> keys;
            private final int count;
            private ListNode prev;
            private ListNode next;

            public ListNode() {
                this(-1);
            }

            public ListNode(int count) {
                this.count = count;
                keys = new ArrayList<>();
            }

            public ListNode(int count, String key, ListNode prevNode, ListNode nextNode) {
                this(count);
                this.keys.add(key);
                this.prev = prevNode;
                this.next = nextNode;
                prevNode.next = this;
                nextNode.prev = this;
            }
        }
    }

    public static void main(String[] args) {
        AllOne allOne = new AllOne();
        allOne.inc("hello");
        allOne.inc("hello");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
        allOne.inc("leet");
        System.out.println(allOne.getMaxKey());
        System.out.println(allOne.getMinKey());
    }


}
